package com.company.zijie;
//只能用递归求fibo
//问int的取值返回答错了：
// int占4个字节32位，32位就是jvm仅仅给分配32个格子的空间，用以存放数据。所以取值范围是+/- 2^31
public class fibo {
    public static void main(String[] args) {
        int n = 4;
        //f(3) = 2 f(4) = 4 f(5)=8
        cache = new int[n+1];
        cache[0] = 0;
        cache[1] = cache[2] = 1;
        System.out.println(f(n));
    }

    static int[] cache;
    public static int f(int n){
        if (n==0) return 0;
        if (n<=2) return 1;
        if(cache[n]!=0) return cache[n];
        int ret = f(n-1)+f(n-2);
        cache[n]= ret;
        return ret;
    }
}
